/**
 * https://leetcode-cn.com/problems/word-break/
 * 单词拆分
 * 给你一个字符串 s 和一个字符串列表 wordDict 作为字典，判定 s 是否可以由空格拆分为一个或多个在字典中出现的单词。说明：拆分时可以重复使用字典中的单词。
 * @param s
 * @param wordDict
 */
const wordBreak = (s: string, wordDict: string[]): boolean => {
  // 转成set
  const set = new Set(wordDict);

  const len = s.length;

  const dp: boolean[] = new Array(len + 1).fill(false);

  // leetcode ['leet', 'code']
  dp[0] = true;
  for (let i = 1; i <= len; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && set.has(s.substr(j, i - j))) {
        // 找到了一个单词, 结束内存的循环, 继续找下一个
        dp[i] = true;
        break;
      }
    }
  }

  return dp[len];
};

console.log('leetcode'.substr(0, 1))